//https://leetcode.cn/problems/longest-common-subsequence/
package codeRandomThoughts.Test1143最长公共子序列;

public class Solution {
    public static int longestCommonSubsequence(String text1, String text2) {
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();

        //dp[i][j]:长度为0-i的字符串text1与长度为0-j的字符串text2的最长公共子序列的长度
        int[][] dp = new int[chars1.length][chars2.length];

        //初始化
        boolean flag = false;
        for (int i = 0; i < chars1.length; i++) {
            if (chars1[i] == chars2[0]) {
                flag = true;
            }
            if (flag) dp[i][0] = 1;
        }
        flag = false;
        for (int j = 0; j < chars2.length; j++) {
            if (chars2[j] == chars1[0]) {
                flag = true;
            }
            if (flag) dp[0][j] = 1;
        }


        if (chars1.length == 1 || chars2.length == 1) {
            return dp[chars1.length - 1][chars2.length - 1];
        }

        //开始递推
        for (int i = 1; i < chars1.length; i++) {
            for (int j = 1; j < chars2.length; j++) {
                if (chars1[i] == chars2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }


        for (int i = 0; i < chars1.length; i++) {
            for (int j = 0; j < chars2.length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        return dp[chars1.length - 1][chars2.length - 1];
    }

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println(longestCommonSubsequence(text1, text2));
    }
}
